package org.example.Soution003;

import java.util.PriorityQueue;

public class MidumInStreamPro {
    public static void main(String[] args) {
        MedianFinder2 mf=new MedianFinder2();
        mf.addNum(-1);
        System.out.println(mf.findMedian());
        mf.addNum(-2);
        System.out.println(mf.findMedian());
        mf.addNum(-3);
        System.out.println(mf.findMedian());
        mf.addNum(-4);
        System.out.println(mf.findMedian());
        mf.addNum(-5);
        System.out.println(mf.findMedian());
    }
}

class MedianFinder2 {
    PriorityQueue<Integer> minHeap;
    PriorityQueue<Integer> maxHeap;

    public MedianFinder2() {
        minHeap=new PriorityQueue<>((a,b)->b-a);
        maxHeap=new PriorityQueue<>((a,b)->a-b);
    }

    public void addNum(int num) {
        if(minHeap.size()==0||minHeap.peek()>=num){
            minHeap.add(num);
            if(maxHeap.size()+1<minHeap.size()){
                maxHeap.add(minHeap.poll());
            }
        }else{
            maxHeap.add(num);
            if(minHeap.size()<maxHeap.size()){
                minHeap.add(maxHeap.poll());
            }
        }
    }

    public double findMedian() {
        if(minHeap.size()==maxHeap.size()){
            return (minHeap.peek()+maxHeap.peek())/2.0;
        }else{
            return minHeap.peek();
        }
    }
}